package sort;

public class HeapSort {
	public static void heapSort(int[] arr) {
		createHeap(arr);
		int end=arr.length-1;
		while(end>0) {
			Swap.swap(arr, 0, end);
			shiftDown(arr,0, end);
			end--;
		}
	}
	
	public static void createHeap(int[] array) {
		int size=array.length;
    	for(int i=(size-1-1)/2;i>=0;i--) {
    		shiftDown(array,i, size);
    	}
    }

    //i为要调整的位置
    //size为数组实际大小
    //向下调整的时间复杂度：O(logn)
    private static void shiftDown(int[] array,int i,int size) {
    	int child=2*i+1;
    	while(child<size) {  //只有节点有孩子就进循环
			//获取孩子节点最大值所在下标
    		//1.如果无右孩子=》index=child   
    		//2.有左右孩子  =》index=elem[child]<elem[child+1]?child+1:child
    		int maxPos=(child+1<size)&&(array[child]<=array[child+1])?child+1:child;
    		//如果已经是大根堆，则无需调整
    		if(array[maxPos]<=array[i]) {
    			break;
    		}
    		//节点交换，位置更新
    		Swap.swap(array,i,maxPos);
    		i=maxPos;
    		child=2*i+1;
    	}
    }
    public static void main(String[] args) {
		int[] arr=new int[]{1,9,7,6,0,5,3,8};
		heapSort(arr);
		for(int x:arr) 
			System.out.print(x+" ");
	}
    
}
